package com.cskaoyan.com.mylist;

import java.util.Objects;

/**
 * 使用双向链表, 实现一个数据结构为线性表的数据容器/集合类
 *
 * 集合类:
 *       1, 使用
 *       2, 底层
 *       3, 逻辑
 */
public class MyDBLinkedList {

    private Node head; // MyDBLinkedList底层所持有的双向链表的头结点
    private Node end;  // MyDBLinkedList底层所持有的双向链表的尾结点
    private int size;  // MyDBLinkedList链表中存储的数据量


    /**
     * MyDBLinkedList的根据内容的添加方法
     * @param str: 要添加的内容
     * @return: 添加是否成功
     */
    public boolean add(String str){

        // 判断链表是否为空
        if (isEmpty()){
            // 新添加的内容, 既是头结点, 又是尾结点
            head = new Node(str);
            end = head;
            size++;
            return true;
        }

        Node node = new Node(str);
        node.pre = end;
        end.next = node;
        end = node;
        // 简化为
        // end.next = new Node(end, str, null);
        // end = end.next;
        size++;

        return true;
    }

    /**
     * MyDBLinkedList根据内容的删除方法
     * @param str: 要删除的内容
     * @return: 删除是否成功
     */
    public boolean remove(String str){
        // 判断链表是否为空
        if (isEmpty()){
            return false;
        }


        // 判断删除的是否是头结点
        if (Objects.equals(str, head.value)){
            // 删除就是头结点

            // 判断一个特殊情况: 链表只剩一个结点了
            if (size == 1){
                // 只剩一个结点, 还被删除了
                head = null;
                end = null;
            } else {
                // 剩多个
                head = head.next;
                head.pre = null;
            }
            size--;
            return true;
        }

        // 处理尾的删除
        if (Objects.equals(str, end.value)){
            // 删除就是尾结点
            end = end.pre;
            end.next = null;
            size--;
            return true;
        }

        // 删除中间某个位置的数据
        Node mid = head; // 定义一个遍历结点

        // mid的下一个结点存在, 并且下一个结点不是要查找的内容, 向后遍历
        while (mid.next != null && !Objects.equals(str, mid.next.value)){
            mid = mid.next;
        }

        // 1, 第一个跳出条件
        if (mid.next == null){
            // 链表遍历完了, 都没有找到这个要删除的内容
            return false;
        }

        // 2, 肯定是找到了这个要删除的内容, 同时mid是要删除结点的:前一个

        // 这个removeNode才是那个真正要删除的中间结点
        Node removeNode = mid.next;

        removeNode.next.pre = removeNode.pre;
        removeNode.pre.next = removeNode.next;
        size--;

        return true;
    }

    /**
     * 根据内容的查找方法
     * @param str: 要查找的内容
     * @return: 这个元素是否存在
     */
    public boolean contains(String str){
        // 判断是否还有数据  查找
        if (isEmpty()){
            // 链表为空
            // 抛异常
            return false;
        }

        Node mid = head;
        // 当前遍历结点存在,  而且当前遍历结点存储的内容也不是要找的值 --> 向后遍历
        while (mid != null && !Objects.equals(str, mid.value)){
            mid = mid.next;
        }

        // 这个链表根本没有存储这个内容
        if (mid == null){
            return false;
        }
        return true;
    }

    /**
     * 根据内容的替换方法
     * @param oldValue: 要被替换的旧值
     * @param newValue: 用来替换的新值
     * @return: 替换是否成功
     */
    public boolean set(String oldValue, String newValue){
        // 判断是否还有数据  查找
        if (isEmpty()){
            // 链表为空
            // 抛异常
            return false;
        }

        Node mid = head;
        // 当前遍历结点存在,  而且当前遍历结点存储的内容也不是要找的值 --> 向后遍历
        while (mid != null && !Objects.equals(oldValue, mid.value)){
            mid = mid.next;
        }

        // 这个链表根本没有存储这个旧值内容
        if (mid == null){
            return false;
        }

        // 找到了 --> 替换
        mid.value = newValue;
        return true;
    }

    /**
     * 根据下标的添加方法
     * @param index: 要添加的下标位置
     * @param str: 要添加的内容
     * @return: 添加是否成功
     */
   public boolean add(int index, String str){
       // 判断下标是否合法
       if (index < 0 || index > size){
           throw new IllegalArgumentException("paramer is Illegal");
       }

       // 判断添加的是否是头位置
       if (index == 0){
           // 必然添加的是头位置

           // 特殊情况, 链表为空
           if (isEmpty()){
               // 链表为空, 新添加的结点既是头结点又是尾结点
               head = new Node(str);
               end = head;
           }else {
               head.pre = new Node(null, str, head);
               head = head.pre;
           }
           size++;
           return true;
       }

       // 判断添加的是否是尾位置
       if (index == size){
           // 添加的位置必然是尾部
           return add(str);
       }

       // 添加到中间位置
       Node mid = head;
       int tag = 1;

       if (index < size/2){
           // 偏头的位置 --> 从前向后遍历

           while (tag != index){
               mid = mid.next;
               tag++;
           }
           // mid是要添加位置的: 前一个

       }else {
           // 偏尾位置 --> 从后/尾向前遍历
           mid = end;
           tag = size;

           while (tag != index){
               mid = mid.pre;
               tag--;
           }
           // mid是要添加位置的:前一个
       }

       // mid是要添加位置的前一个位置
       Node node = new Node(str);
       node.next = mid.next;
       node.pre = mid;
       mid.next = node;
       mid.next.pre = node;

//       mid.next = new Node(mid, str, mid.next);
//       mid.next.next.pre = mid.next;
       size++;
       return true;
   }

    /**
     * 根据下标的删除方法
     * @param index: 要删除的下标位置
     * @return: 删除是否成功
     */
   public String remove(int index){
       if (index < 0 || index >= size){
           throw new IllegalArgumentException("paramer is Illegal");
       }
       // 删除的是头位置
       if (index == 0){
           // 特殊情况, 只剩一个结点了
           String oldValue = head.value;
           if (size == 1){
               // 又要删除这仅剩一个结点--> 头尾置位null
               head = null;
               end = null;
           }else {
               // 剩余多个结点
               head = head.next;
               head.pre = null;
           }
           size--;
           return oldValue;
       }

       // 处理尾的删除
       if (index == size-1){
           String oldValue = end.value;

           end = end.pre;
           end.next = null;
           size--;
           return oldValue;
       }

       // 删除中间某个置位了: 先根据下标找到
       // 添加到中间位置
       Node mid = head;
       int tag = 1;

       if (index < size/2){
           // 偏头的位置 --> 从前向后遍历

           while (tag != index){
               mid = mid.next;
               tag++;
           }
           // mid是要删除位置的: 前一个

       }else {
           // 偏尾位置 --> 从后/尾向前遍历
           mid = end;
           tag = size;

           while (tag != index){
               mid = mid.pre;
               tag--;
           }
           // mid是要删除位置的:前一个
       }

       // mid是要删除位置的前一个结点
       Node removeNode = mid.next;

       removeNode.next.pre = removeNode.pre;
       removeNode.pre.next = removeNode.next;
       size--;

       return removeNode.value;
   }

    /**
     * 根据下标的查找
     * @param index: 要查找的下标位置
     * @return: 这个下标位置存储的内容
     */
   public String get(int index){
       if (index < 0 || index >= size){
           throw new IllegalArgumentException("paramer is Illegal");
       }

       // 偏头偏尾
       Node mid = head;
       int tag = 0;

       if (index < size/2){
           // 偏头的位置 --> 从前向后遍历
           while (tag != index){
               mid = mid.next;
               tag++;
           }
       }else {
           // 偏尾位置 --> 从后/尾向前遍历
           mid = end;
           tag = size-1;
           while (tag != index){
               mid = mid.pre;
               tag--;
           }
       }

       // mid就是我们要查找的位置
       return mid.value;
   }

    /**
     * 根据下标的修改方法
     * @param index: 要修改的下标位置
     * @param newValue: 用来覆盖的新值
     * @return: 被修改/被覆盖的旧值
     */
   public String set(int index, String newValue){
       if (index < 0 || index >= size){
           throw new IllegalArgumentException("paramer is Illegal");
       }
       // 偏头偏尾
       Node mid = head;
       int tag = 0;

       if (index < size/2){
           // 偏头的位置 --> 从前向后遍历
           while (tag != index){
               mid = mid.next;
               tag++;
           }
       }else {
           // 偏尾位置 --> 从后/尾向前遍历
           mid = end;
           tag = size-1;
           while (tag != index){
               mid = mid.pre;
               tag--;
           }
       }
       // mid就是我们要查找的位置 --> 替换
       String oldValue = mid.value; // 保存旧值
       mid.value = newValue;

       return oldValue;
   }



    public int size(){
        return size;
    }
    public boolean isEmpty(){
        return size == 0;
    }

    // 双向链表的结点类型
    class Node{
        String value; // 值域
        Node pre;     // 前指针域
        Node next;    // 后指针域

        public Node(String value) {
            this.value = value;
        }

        public Node( Node pre, String value, Node next) {
            this.value = value;
            this.pre = pre;
            this.next = next;
        }
    }
}
